package 算法基础模板.chapter_02;

/**
 * @author Summerday
 */
public class StringHash {

    final int T = 131;
    int[] p, h;
    int N;

    StringHash (String s, int n) {
        N = n;
        p = new int[n + 1];
        h = new int[n + 1];
        p[0] = 1;
        for (int i = 1; i <= n; i++) {
            p[i] = p[i - 1] * T;
            h[i] = h[i - 1] * T + s.charAt(i - 1);
        }
    }

    public long getHash (int l, int r) {
        return h[r] - h[l - 1] * p[r - l + 1];
    }

}
